#include "graph_support/TestMinCostFlow.h"

#include "graph_support/impls/compact/CompactGraph.h"

#include "graph_support/attributes/CostFlowEdgeAttributes.h"
#include "graph_support/alg/flow/Dinic.h"
#include "graph_support/alg/flow/MinCostFlow.h"

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"
#include "graph_support/utils/CollectionsInit.h"


using namespace GRAPH_SUPPORT_NS::attributes;
using namespace GRAPH_SUPPORT_NS::utils;
using namespace GRAPH_SUPPORT_NS::alg::flow;
using namespace GRAPH_SUPPORT_NS::impls::compact;

typedef CostFlowEdgeAttributesTmpl< double > CFEdgeAttributes;
typedef CompactGraphTmpl< int, CFEdgeAttributes > CFGraph;
typedef CompactGraphTmpl< const char *, CFEdgeAttributes > CFNameGraph;

void TestCostFlowAttributes()
{
	CFEdgeAttributes attributes( 12.34, 34.56 );
	CFEdgeAttributes attributesR;
	attributes.onBidirEdgeCreated( attributesR, true );
	attributesR.onBidirEdgeCreated( attributes, false );

	BOOST_CHECK_CLOSE( 12.34, attributes.getCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( 34.56, attributes.getCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 0.0, attributes.getFlow(), 1e-5 );


	BOOST_CHECK_CLOSE( 0.0, attributesR.getCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( -34.56, attributesR.getCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 0.0, attributes.getFlow(), 1e-5 );

	BOOST_CHECK_CLOSE( 12.34, attributes.getCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( 34.56, attributes.getCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 0.0, attributes.getFlow(), 1e-5 );

	BOOST_CHECK_CLOSE( 0.0, attributesR.getCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( -34.56, attributesR.getCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 0.0, attributes.getFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 12.34, attributes.getRemainCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( 0.0, attributesR.getRemainCapacity(), 1e-5 );

	attributes.addFlow( 1.0 );

	BOOST_CHECK_CLOSE( 1.0, attributes.getFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 11.34, attributes.getRemainCapacity(), 1e-5 );

	BOOST_CHECK_CLOSE( -1.0, attributesR.getFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 1.0, attributesR.getRemainCapacity(), 1e-5 );

	attributes.setCapacity( 98.76 );

	BOOST_CHECK_CLOSE( 98.76, attributes.getCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( 1.0, attributes.getFlow(), 1e-5 );

	BOOST_CHECK_CLOSE( 0.0, attributesR.getCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( -1.0, attributesR.getFlow(), 1e-5 );

	attributes.setCost( 65.43 );

	BOOST_CHECK_CLOSE( 65.43, attributes.getCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 1.0, attributes.getFlow(), 1e-5 );

	BOOST_CHECK_CLOSE( 0.0, attributesR.getCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( -65.43, attributesR.getCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 1.0, attributes.getFlow(), 1e-5 );
}

void TestCostFlowChepExpensive()
{
	CFGraph gr( arr2vector< int >( ( const int [] ) { 0, 1, 2, 3, 4 } ), true );

	gr.addEdge( 0, 1, CFEdgeAttributes( 10, 100 ) );
	gr.addEdge( 0, 2, CFEdgeAttributes( 5, 10 ) );
	gr.addEdge( 2, 1, CFEdgeAttributes( 7, 10 ) );

	Dinic< CFGraph > dinic( gr );
	dinic( 0, 1 );
	BOOST_CHECK_CLOSE( 15.0, dinic.getTotalFlow(), 1e-5 );

	MinCostFlow< CFGraph > mcflow( gr );

	mcflow( 0, 1, 5.0 );
	BOOST_CHECK_CLOSE( 5.0, mcflow.getTotalFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 100.0, mcflow.getTotalCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 5.0, mcflow.getFlow( 0, 2 ), 1e-5 );
	BOOST_CHECK_CLOSE( 50.0, mcflow.getCost( 0, 2 ), 1e-5 );

	mcflow( 0, 1, 7.0 );
	BOOST_CHECK_CLOSE( 7.0, mcflow.getTotalFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 300.0, mcflow.getTotalCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 5.0, mcflow.getFlow( 0, 2 ), 1e-5 );
	BOOST_CHECK_CLOSE( 2.0, mcflow.getFlow( 0, 1 ), 1e-5 );
	BOOST_CHECK_CLOSE( 200.0, mcflow.getCost( 0, 1 ), 1e-5 );

	mcflow( 0, 1, 16.0 );
	BOOST_CHECK_CLOSE( 15.0, mcflow.getTotalFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 1100.0, mcflow.getTotalCost(), 1e-5 );
	BOOST_CHECK_CLOSE( 5.0, mcflow.getFlow( 0, 2 ), 1e-5 );
	BOOST_CHECK_CLOSE( 10.0, mcflow.getFlow( 0, 1 ), 1e-5 );
	BOOST_CHECK_CLOSE( 1000.0, mcflow.getCost( 0, 1 ), 1e-5 );
}

void TestCostFlowNegativeCycleCancel()
{
	CFNameGraph gr( arr2vector< const char * >( ( const char * const [] ) { "Q", "W", "E", "R", "T", "Y", "U", "I" } ), true );

	gr.addEdge( "Q", "W", CFEdgeAttributes( 10, 100 ) );
	gr.addEdge( "Q", "E", CFEdgeAttributes( 5, 100 ) );
	gr.addEdge( "E", "W", CFEdgeAttributes( 5, 100 ) );

	// 0 - cycle
	gr.addEdge( "E", "R", CFEdgeAttributes( 5, 40 ) );
	gr.addEdge( "R", "T", CFEdgeAttributes( 6, -10 ) );
	gr.addEdge( "T", "Y", CFEdgeAttributes( 7, -10 ) );
	gr.addEdge( "Y", "U", CFEdgeAttributes( 6, -10 ) );
	gr.addEdge( "U", "E", CFEdgeAttributes( 5, -10 ) );

	MinCostFlow< CFNameGraph > mcflow( gr );

	mcflow( "Q", "W", 5.0 );
	BOOST_CHECK_CLOSE( 5.0, mcflow.getTotalFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 500.0, mcflow.getTotalCost(), 1e-5 );

	// negative cycle: E -> R -> T -> Y -> U -> I ---> E
	gr.addEdge( "U", "I", CFEdgeAttributes( 5, -10 ) );
	gr.addEdge( "I", "E", CFEdgeAttributes( 5, -10 ) );

	mcflow( "Q", "W", 5.0 );
	BOOST_CHECK_CLOSE( 5.0, mcflow.getTotalFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 450, mcflow.getTotalCost(), 1e-5 );
}

void TestCostFlowNegativeCycleWithChild()
{
	CFNameGraph gr( arr2vector< const char * >( ( const char * const [] ) { "Q", "W", "E", "R", "T", "Y", "U", "I" } ), true );

	gr.addEdge( "Q", "W", CFEdgeAttributes( 10, 100 ) );

	gr.addEdge( "Q", "E", CFEdgeAttributes( 10, 100 ) );
	gr.addEdge( "E", "W", CFEdgeAttributes( 10, 100 ) );

	gr.addEdge( "E", "R", CFEdgeAttributes( 10, -1 ) );
	gr.addEdge( "R", "T", CFEdgeAttributes( 10, -1 ) );
	gr.addEdge( "T", "E", CFEdgeAttributes( 10, -1 ) );

	gr.addEdge( "R", "Y", CFEdgeAttributes( 10, 1 ) );
	gr.addEdge( "Y", "U", CFEdgeAttributes( 10, 1 ) );

	MinCostFlow< CFNameGraph > mcflow( gr );

	mcflow( "Q", "W", 10.0 );
	BOOST_CHECK_CLOSE( 10.0, mcflow.getTotalFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 1000.0 - 30.0, mcflow.getTotalCost(), 1e-5 );

	mcflow( "Q", "W", 20.0 );
	BOOST_CHECK_CLOSE( 20.0, mcflow.getTotalFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 3000.0 - 30.0, mcflow.getTotalCost(), 1e-5 );

	mcflow( "Q", "W", 25.0 );
	BOOST_CHECK_CLOSE( 20.0, mcflow.getTotalFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 3000.0 - 30.0, mcflow.getTotalCost(), 1e-5 );
}

